package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/repeated-dna-sequences/'>重复的DNA序列(Repeated DNA Sequences)</a>
 * <p>
 * DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。
 *     <ul><li>例如，"ACGAATTCCG" 是一个 DNA序列 。</li></ul>
 * </p>
 * <p>在研究 DNA 时，识别 DNA 中的重复序列非常有用。</p>
 * <p>给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
 *      输出：["AAAAACCCCC","CCCCCAAAAA"]
 *
 * 示例 2：
 *      输入：s = "AAAAAAAAAAAAA"
 *      输出：["AAAAAAAAAA"]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>0 <= s.length <= 10^5</li>
 *     <li>s[i]=='A'、'C'、'G' or 'T'</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/8 17:21
 */
public class LC0187RepeatedDNASequences_M {
    static class Solution {

        public List<String> findRepeatedDnaSequences(String s) {
            int L = 10;
            List<String> ansList = new ArrayList<>();
            if (s == null || s.length() <= L) {
                return ansList;
            }
            Map<Character, Integer> bin = new HashMap<Character, Integer>() {{
                put('A', 0);
                put('C', 1);
                put('G', 2);
                put('T', 3);
            }};
            int currStr = 0;
            Map<Integer, Integer> cntMap = new HashMap<>();
            // 用两个二进制位表示一个字符，十个字符共需要20个二进制位，一个整数32位。
            // 1.先将前10个字符转换成二进制数，即一个序列的长度。
            for (int i = 0; i < L; i++) {
                currStr = (currStr << 2) | bin.get(s.charAt(i));
            }
            cntMap.put(currStr, 1);
            // 从第十一个字符串开始。每一次添加一个字符到尾部，并移除开头的字符
            for (int i = L; i < s.length(); i++) {
                // currStr <<= 2 ： 增加一位字符的二进制位，即2位。
                // currStr |= bin.get(s.charAt(i + L - 1))) ==> 将增加的二进制位(00)替换成对应的值。A->00 B->01 ...
                // currStr &= ((1 << (2 * L)) - 1) ==> 将高于20位的二进制位的值置为0，相当于保持字符传的长度为10
                currStr = ((currStr << 2) | bin.get(s.charAt(i))) & ((1 << (2 * L)) - 1);
                Integer cnt = cntMap.getOrDefault(currStr, 0);
                if (cnt == 1) {
                    ansList.add(s.substring(i - L + 1, i + 1));
                }
                cntMap.put(currStr, cnt + 1);
            }
            return ansList;
        }

        public List<String> findRepeatedDnaSequences2(String s) {
            List<String> ansList = new ArrayList<>();
            if (s == null || s.length() <= 10) {
                return ansList;
            }
            Map<String, Integer> cntMap = new HashMap<>();
            for (int i = 0; i <= s.length() - 10; i++) {
                String currStr = s.substring(i, i + 10);
                Integer cnt = cntMap.getOrDefault(currStr, 0);
                if (cnt == 1) {
                    ansList.add(currStr);
                }
                cntMap.put(currStr, cnt + 1);
            }
            return ansList;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListString(solution.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
        Printer.printListString(solution.findRepeatedDnaSequences("AAAAAAAAAAAAA"));
    }
}
